<head>
    <meta charset="UTF-8">
<title>算法训练 2的次幂表示</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>&nbsp;</p>
<p>&nbsp;</p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt">&nbsp;</p>
<p>&nbsp;</p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-size: 14pt; color: black; mso-themecolor: text1"><strong>问题描述<span lang="EN-US"><o:p></o:p></span></strong></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt; mso-char-indent-count: 2.0"><span style="color: black; mso-themecolor: text1"><font size="3">任何一个正整数都可以用<span lang="EN-US">2</span>进制表示，例如：<span lang="EN-US">137</span>的<span lang="EN-US">2</span>进制表示为<span lang="EN-US">10001001</span>。<span lang="EN-US"><o:p></o:p></span></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span style="color: black; mso-themecolor: text1">将这种<span lang="EN-US">2</span>进制表示写成<span lang="EN-US">2</span>的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">137=2^7+2^3+2^0</span><span lang="EN-US" style="color: black; mso-themecolor: text1"><o:p></o:p></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">&nbsp;&nbsp;</span><span style="color: black; mso-themecolor: text1">现在约定幂次用括号来表示，即</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">a^b</span><span style="color: black; mso-themecolor: text1">表示为</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">a</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">b</span><span style="color: black; mso-themecolor: text1">）<span lang="EN-US"><o:p></o:p></span></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">&nbsp;&nbsp;</span><span style="color: black; mso-themecolor: text1">此时，</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">137</span><span style="color: black; mso-themecolor: text1">可表示为：</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">7</span><span style="color: black; mso-themecolor: text1">）</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">3</span><span style="color: black; mso-themecolor: text1">）</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">0</span><span style="color: black; mso-themecolor: text1">）<span lang="EN-US"><o:p></o:p></span></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">&nbsp;&nbsp;</span><span style="color: black; mso-themecolor: text1">进一步：</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">7=2^2+2+2^0<span style="mso-spacerun: yes">&nbsp; </span></span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2^1</span><span style="color: black; mso-themecolor: text1">用</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2</span><span style="color: black; mso-themecolor: text1">表示）<span lang="EN-US"><o:p></o:p></span></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">&nbsp;&nbsp;<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>3=2+2^0<sup>&nbsp;&nbsp;</sup></span><span lang="EN-US" style="color: black; mso-themecolor: text1"><o:p></o:p></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">&nbsp;&nbsp;</span><span style="color: black; mso-themecolor: text1">所以最后</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">137</span><span style="color: black; mso-themecolor: text1">可表示为：</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2</span><span style="color: black; mso-themecolor: text1">）</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">+2+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">0</span><span style="color: black; mso-themecolor: text1">））</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">0</span><span style="color: black; mso-themecolor: text1">））</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">0</span><span style="color: black; mso-themecolor: text1">）<span lang="EN-US"><o:p></o:p></span></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">&nbsp;&nbsp;</span><span style="color: black; mso-themecolor: text1">又如：</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">1315=2^10+2^8+2^5+2+1</span><span lang="EN-US" style="color: black; mso-themecolor: text1"><o:p></o:p></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">&nbsp;&nbsp;</span><span style="color: black; mso-themecolor: text1">所以</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">1315</span><span style="color: black; mso-themecolor: text1">最后可表示为：<span lang="EN-US"><o:p></o:p></span></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">&nbsp;&nbsp;2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">0</span><span style="color: black; mso-themecolor: text1">））</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">+2</span><span style="color: black; mso-themecolor: text1">）</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">0</span><span style="color: black; mso-themecolor: text1">）））</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2</span><span style="color: black; mso-themecolor: text1">）</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">0</span><span style="color: black; mso-themecolor: text1">））</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">+2+2</span><span style="color: black; mso-themecolor: text1">（</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">0</span><span style="color: black; mso-themecolor: text1">）<span lang="EN-US"><o:p></o:p></span></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1"><o:p><font size="3">&nbsp;</font></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-size: 14pt; color: black; mso-themecolor: text1"><strong>输入<span lang="EN-US"><o:p></o:p></span></strong></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span style="color: black; mso-themecolor: text1">正整数（<span lang="EN-US">1&lt;=</span></span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">n</span><span lang="EN-US" style="color: black; mso-themecolor: text1">&lt;=</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">20000</span><span style="color: black; mso-themecolor: text1">）<span lang="EN-US"><o:p></o:p></span></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1"><o:p><font size="3">&nbsp;</font></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-size: 14pt; color: black; mso-themecolor: text1"><strong>输出<span lang="EN-US"><o:p></o:p></span></strong></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span style="color: black; mso-themecolor: text1">符合约定的</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">n</span><span style="color: black; mso-themecolor: text1">的</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">0</span><span style="color: black; mso-themecolor: text1">，</span><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">2</span><span style="color: black; mso-themecolor: text1">表示（在表示中不能有空格）<span lang="EN-US"><o:p></o:p></span></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="color: black; mso-themecolor: text1"><o:p><font size="3">&nbsp;</font></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-size: 14pt; color: black; mso-themecolor: text1"><strong>样例输入<span lang="EN-US">1<o:p></o:p></span></strong></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="color: black; mso-themecolor: text1"><font size="3">137<o:p></o:p></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="color: black; mso-themecolor: text1"><o:p><font size="3">&nbsp;</font></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-size: 14pt; color: black; mso-themecolor: text1"><strong>样例输出<span lang="EN-US">1<o:p></o:p></span></strong></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1"><font size="3">2(2(2)+2+2(0))+2(2+2(0))+2(0)<o:p></o:p></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="color: black; mso-themecolor: text1"><o:p><font size="3">&nbsp;</font></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-size: 14pt; color: black; mso-themecolor: text1"><strong>样例输入<span lang="EN-US">2<o:p></o:p></span></strong></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="color: black; mso-themecolor: text1"><font size="3">1315<o:p></o:p></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="color: black; mso-themecolor: text1"><o:p><font size="3">&nbsp;</font></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-size: 14pt; color: black; mso-themecolor: text1"><strong>样例输出<span lang="EN-US">2<o:p></o:p></span></strong></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1"><font size="3">2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)<o:p></o:p></font></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1"><o:p><font size="3">&nbsp;</font></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="color: red; mso-bidi-font-family: 'Times New Roman'"><strong><font size="3">提示<span lang="EN-US"><o:p></o:p></span></font></strong></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><font size="3"><span lang="EN-US" style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1"><span style="mso-tab-count: 1">&nbsp;&nbsp;&nbsp; </span></span><span style="color: black; mso-bidi-font-family: 'Times New Roman'; mso-themecolor: text1">用递归实现会比较简单，可以一边递归一边输出<span lang="EN-US"><o:p></o:p></span></span></font></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt">&nbsp;</p>